package avltree;

import bst.BSTImpl;
import bst.BSTNode;


/**
 * Projeto : Arvore Preta e Vermelha
 * 
 * Equipe:
 * 			Antonio Eduardo
 * 			Gabriel de Brito
 * 			Gervasio Costa
 * 			Jordan Ferreira
 * 			Wesley Breno
 * 
 */

public class AVLTreeImpl<T extends Comparable<T>> extends BSTImpl<T> implements
		AVLTree<T> {

	// AUXILIARY
	protected int calculateBalance(BSTNode<T> node) {
		return height((BSTNode<T>) node.getLeft())
				- height((BSTNode<T>) node.getRight()); // X < 0 Direita, X =
															// 0 Balanceado, X >
															// 0 Esquerda
	}

	// AUXILIARY
	protected void rebalance(BSTNode<T> node) {
		int balance = calculateBalance(node);
		if (Math.abs(balance) > 1) {
			if (calculateBalance((BSTNode<T>) node) > 0
					&& calculateBalance((BSTNode<T>) node.getLeft()) >= 0)
				rightRotation(node); // Left-Left
			else if (calculateBalance((BSTNode<T>) node) < 0
					&& calculateBalance((BSTNode<T>) node.getRight()) <= 0)
				leftRotation(node); // Right-Right
			else if (calculateBalance((BSTNode<T>) node) > 0
					&& calculateBalance((BSTNode<T>) node.getLeft()) < 0) { // Left-Right
				leftRotation((BSTNode<T>) node.getLeft());
				rightRotation(node);
			} else if (calculateBalance((BSTNode<T>) node) < 0
					&& calculateBalance((BSTNode<T>) node.getRight()) > 0) {
				rightRotation((BSTNode<T>) node.getRight());
				leftRotation(node);
			}
		}
	}

	// AUXILIARY
	protected void rebalanceUp(BSTNode<T> node) {
		BSTNode<T> parent = (BSTNode<T>) node.getParent();
		while (parent != null) {
			rebalance(parent);
			parent = (BSTNode<T>) parent.getParent();
		}
	}
	protected void leftRotation(BSTNode<T> node) {
		BSTNode<T> pivot = (BSTNode<T>) node.getRight();
		node.setRight(pivot.getLeft());
		node.getRight().setParent(node);
		pivot.setLeft(node);
		pivot.setParent(node.getParent());
		BSTNode<T> nodePai = (BSTNode<T>) pivot.getParent();
		if (nodePai != null) {
			if (node.equals(nodePai.getRight())) {
				nodePai.setRight(pivot);
			} else {
				nodePai.setLeft(pivot);
			}
		}
		node.setParent(pivot);
		if (node.equals(root)) {
			root = pivot;
		}
	}

	// AUXILIARY
	protected void rightRotation(BSTNode<T> node) {
		BSTNode<T> pivot = (BSTNode<T>) node.getLeft();
		node.setLeft(pivot.getRight());
		node.getLeft().setParent(node);
		pivot.setRight(node);
		pivot.setParent(node.getParent());
		BSTNode<T> nodePai = (BSTNode<T>) pivot.getParent();
		if (nodePai != null) {
			if (node.equals(nodePai.getRight())) {
				nodePai.setRight(pivot);
			} else {
				nodePai.setLeft(pivot);
			}
		}
		node.setParent(pivot);
		if (node.equals(root)) {
			root = pivot;
		}
	}


	protected void miniRotationRigthLeft(BSTNode<T> node) {
		BSTNode<T> nodeAux = (BSTNode<T>) node.getRight();
		node.setRight(node.getRight().getLeft());
		node.getRight().setParent(node);
		nodeAux.setLeft(NIL);
		nodeAux.setParent(node.getRight());
		node.getRight().setRight(nodeAux);
	}

	protected void miniRotationLeftRigth(BSTNode<T> node) {
		
		BSTNode<T> nodeAux = (BSTNode<T>) node.getLeft();
		node.setLeft(node.getLeft().getRight());
		node.getLeft().setParent(node);
		nodeAux.setRight(NIL);
		nodeAux.setParent(node.getLeft());
		node.getLeft().setLeft(nodeAux);
	}

	public void insert(T element) {
		insertAux(root, element);
	}
	
	@Override
	public BSTNode<T> search(T element) {
		return (BSTNode<T>) super.search(element);
	}

	public void insertAux(BSTNode<T> node, T element) {
		if (node.isEmpty()) {
			node.setData(element);
			node.setLeft(new BSTNode<T>());
			node.setRight(new BSTNode<T>());
		} else {
			if (element.compareTo(node.getData()) < 0) {
				insertAux((BSTNode<T>) node.getLeft(), element);
			} else if (element.compareTo(node.getData()) > 0) {
				insertAux((BSTNode<T>) node.getRight(), element);
			}
			rebalance(node);
		}
	}

	private BSTNode<T> removeAux(T element, BSTNode<T> node) {
		if (node.isEmpty()) {
			return root;
		}
		if (element.compareTo(node.getData()) < 0) {
			node.setLeft(removeAux(element, (BSTNode<T>) node.getLeft()));
		} else if (element.compareTo(node.getData()) > 0) {
			node.setRight(removeAux(element, (BSTNode<T>) node.getRight()));
		} else if (!(node.getLeft().isEmpty()) && !(node.getRight().isEmpty())) {
			node.setData(minimumAux((BSTNode<T>) node.getRight()).getData());
			node.setRight(removeMin((BSTNode<T>) node.getRight()));
		} else {
			if (!(node.getLeft().isEmpty())) {
				node = (BSTNode<T>) node.getLeft();
			} else {
				node = (BSTNode<T>) node.getRight();
			}
		}
		rebalanceUp(node);
		return node;
	}

	private BSTNode<T> removeMin(BSTNode<T> node) {
		if (node.isEmpty()) {
			return node;
		} else if (!(node.getLeft().isEmpty())) {
			node.setLeft(removeMin((BSTNode<T>) node.getLeft()));
			return node;
		} else {
			node = (BSTNode<T>) node.getRight();
			return node;
		}
	}

	private BSTNode<T> minimumAux(BSTNode<T> node) {
		if (node == null || node.isEmpty()) {
			return null;
		} else {
			if (node.getLeft().isEmpty()) {
				return node;
			} else {
				return minimumAux((BSTNode<T>) node.getLeft());
			}
		}
	}

}